package com.example.java.yugutou.chapter1_linklist.level2.topic2_1第一个公共结点;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * @Author : 佩萁
 * Description :
 * @Create : 2023/12/1 - 14:40
 */
public class FindFirstCommonNode {
    public static void main(String[] args) throws InterruptedException {
        //初始化链表
        ListNode[] heads = initLinkedList();
        //从初始化的链表中取出里面含有的两个子链表
        ListNode la = heads[0];
        ListNode lb = heads[1];
        //case值，用来选择方法时使用
        int testMethod = 3;
        //初始化一个结点，用来接收公共结点
        ListNode node = new ListNode(0);
        switch (testMethod) {
            case 1:
                node = findFirstCommonNodeByMap(la, lb);
                break;
            case 2:
                node = findFirstCommonNodeBySet(la, lb);
                break;
            case 3:
                node = findFirstCommonNodeByStack(la, lb);
        }
        //打印公共结点的值
        System.out.println("公共结点为:" + node.val);
    }

    /**
     * 方法1：通过Hash辅助查找
     *
     * @ param pHead1
     * @ param pHead2
     */
    public static ListNode findFirstCommonNodeByMap(ListNode pHead1, ListNode pHead2) {
        //先判断传入的链表头指针是否有空的，如果有空，说明这个是个空链表，也就没有公共结点了
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        //当前指针指向
        ListNode current1 = pHead1;
        ListNode current2 = pHead2;
        HashMap<ListNode, Integer> hashMap = new HashMap<ListNode, Integer>();
        while (current1 != null) {
            //先将一个链表放进map里，然后一边遍历第二个链表，一边看hash中是否存在当前节点，如果有相同结点，皆可以检测出来
            hashMap.put(current1, null);
            current1 = current1.next;//当前指针通过这条语句不停后移，然后把所有元素就放进了hash中
        }
        while (current2 != null) {
            if (hashMap.containsKey(current2)) {
                //containsKey()检查hash中是否包含current2键
                //因为如果是公共结点，那么二者的指针应该是一样的，所以键相同
                return current2;//执行到这里已经找到公共结点了
            }
            current2 = current2.next;//如果没有找到公共结点就不断的往后移动，获得新的当前current2指针
        }
        return null;
    }


    /**
     * 方法2：通过集合来辅助查找
     *
     * @param headA
     * @param headB
     */
    public static ListNode findFirstCommonNodeBySet(ListNode headA, ListNode headB) {
        //初始化一个set集合
        Set<ListNode> set = new HashSet<>();
        //步骤和方法1差不多
        //如果headA不为空，说明当前指针后面是有元素的，就将其先添加到set中
        while (headA != null) {
            set.add(headA);
            headA = headA.next;//指针后移
        }
        //先判断headB是否为空，如果为空，直接返回null
        while (headB != null) {
            //如果不为空，查看set中是否含有headB，即是否含有公共结点
            if (set.contains(headB)) {
                //含有公共结点，返回headB
                return headB;
            }
            //不含有移动指针到下一个，重复上面的操作查找set中是否含有
            headB = headB.next;
        }
        return null;
    }


    /**
     * 方法3：通过栈
     */
    public static ListNode findFirstCommonNodeByStack(ListNode headA, ListNode headB) {
        Stack<ListNode> stackA = new Stack<>();
        Stack<ListNode> stackB = new Stack<>();
        while (headA != null) {
            stackA.push(headA);
            headA = headA.next;
        }
        while (headB != null) {
            //push()将元素添加到栈的顶部，成为新的栈顶元素
            stackB.push(headB);
            //指针移动到当前元素
            headB = headB.next;
        }
        //初始化结点
        ListNode preNode = null;
        while (stackB.size() > 0 && stackA.size() > 0) {
            //peek()查看栈顶元素，但不将其从栈中移除
            //外层循环不断循环，这里不断判断A B栈顶元素是否相等，如果相等就给preNode重新赋值
            //当不相等时就跳出循环，如果没有公共节点，第一次判断就会跳出循环，
            //如果有公共节点并且不止一个公共节点，怎么找第一个公共节点呢？
            //这里其实已经解决了，有公共节点就给preNode重新赋值呗，所以当栈顶元素不相等时
            //此时的preNode就是第一个公共节点
            if (stackA.peek() == stackB.peek()) {
                //pop()弹出，从栈的顶部移出元素，返回元素值，并将站顶指针移动到下一个元素
                preNode = stackA.pop();//弹出节点并且指针移动
                stackB.pop();//B也移动指针
            } else {
                break;
            }
        }
        return preNode;
    }

    /**
     * 方法4：通过序列拼接
     */


    //结点类
    static class ListNode {
        public int val;
        public ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    /**
     * 构造两个链表,这里是简单构建
     */
    private static ListNode[] initLinkedList() {
        ListNode[] heads = new ListNode[2];//创建一个链表存放两个链表的头指针
        //构建第一个链表交点之前的元素1 ->2->3 ->4 ->5 ->6
        heads[0] = new ListNode(1);//第一个位置
        ListNode current1 = heads[0];
        current1.next = new ListNode(2);
        current1 = current1.next;
        current1.next = new ListNode(3);
        current1 = current1.next;

        //11-> 22 -> 4 ->5 ->6
        //构建第二个链表交点之前的元素
        heads[1] = new ListNode(11);//第二个位置
        ListNode current2 = heads[1];//当前结点指向头指针
        current2.next = new ListNode(22);//指向下一个结点
        current2 = current2.next;
        //构建公共结点以及之后的元素
        ListNode node4 = new ListNode(4);
        //两个链表都指向公共结点
        current1.next = node4;
        current2.next = node4;
        //公共结点的下一个结点
        ListNode node5 = new ListNode(5);
        node4.next = node5;

        ListNode node6 = new ListNode(6);
        node5.next = node6;
        return heads;//返回存放两个链表头指针的链表
    }
}
